Shortest Path
Q11.
Let G = (V,E) be an undirected graph with a sub-graph G1 = (V1,E1), Weight are assigned to edges of G as follows w(e)=\left\{\begin{matrix} 0 &if \; e \in E, \\ 1& otherwise \end{matrix}\right. A single-source shortest path algorithm is executed on the weighted graph (V,E,w) with an arbitrary vertex v1 of V1 as the source. Which of the following can always be inferred from the path costs computed?Q12.
Which of the following statement(s) is/are correct regarding Bellman-Ford shortest path algorithm? P. Always finds a negative weighted cycle, if one exists. Q. Finds whether any negative weighted cycle is reachable from the source.Q13.
In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity, byQ14.
Let s and t be two vertices in a undirected graph G=(V, E) having distinct positive edge weights. Let [X, Y] be a partition of V such that s\inX and t\inY. Consider the edge e having the minimum weight amongst all those edges that have one vertex in X and one vertex in Y. Let the weight of an edge e denote the congestion on that edge. The congestion on a path is defined to be the maximum of the congestions on the edges of the path. We wish to find the path from s to t having minimum congestion. Which one of the following paths is always such a path of minimum congestion?Q15.
Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry W_{ij} in the matrix W below is the weight of the edge {i, j}. \begin{pmatrix} 0&1 & 8 & 1 &4 \\ 1& 0 & 12 & 4 & 9\\ 8 & 12 & 0 & 7 & 3\\ 1& 4& 7 & 0 &2 \\ 4& 9 & 3& 2 &0 \end{pmatrix}What is the minimum possible weight of a path P from vertex 1 to vertex 2 in this graph such that P contains at most 3 edges?Q16.
Consider the weighted undirected graph with 4 vertices,where the weigh to edge {i, j} is given by the entry Wij in the matrix W. W=\begin{bmatrix} 0 & 2&8 & 5\\ 2& 0& 5 &8 \\ 8 & 5 & 0& x\\ 5&8 & x&0 \end{bmatrix} The largest possible integer value of x, for which at least one shortest path between some pair of vertices will contain the edge with weight x is ____.Q17.
To implement Dijkstra's shortest path algorithm on unweighted graphs so that it runs in linear time, then data structure to be used isQ18.
Consider the undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r . Let d(r,u) and d(r,v) be the lengths of the shortest paths form r to u and v respectively in G. If u is visited before v during the breadth-first traversal, which of the following statements is correct ?Q19.
Let G(V,E) be an undirected graph with positive edge weights. Dijkstra's single source shortest path algorithm can be implemented using the binary heap data structure with time complexity:Q20.
Suppose we run Dijkstra's single source shortest-path algorithm on the following edge-weighted directed graph with vertex P as the source. In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized?